package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Arrays;
import java.util.Scanner;

/*
给出N个物体，第i个物体重量为wi。选择尽量多的物体，使得总重量不超过maxWight
返回最多装了几个物体

in
6
1 2 3 4 5 6
20

out
5
1 2 3 4 5
 */
public class e背包问题by贪心plus不可切割尽可能多装 {
	public static void main(String[] args) {
		e背包问题by贪心plus不可切割尽可能多装 test = new e背包问题by贪心plus不可切割尽可能多装();
//		test.useGreedyAlgorithmKnapsack1();
		test.useGreedyAlgorithmKnapsack1HaveCount();
	}
	
	/**
	 * 前置方法
	 */
	public void useGreedyAlgorithmKnapsack1() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] weight = new int[N];
		for (int i = 0; i < N; i++) {
			weight[i] = scanner.nextInt();
		}
		int maxWight = scanner.nextInt();
		Arrays.sort(weight);
		int res = GreedyAlgorithmKnapsack1(weight, N, maxWight);
		System.out.println(res);
	}
	
	/**
	 * 贪心，每次拿最轻的
	 * @param weight
	 * @param n
	 * @param maxWeight
	 * @return
	 */
	public int GreedyAlgorithmKnapsack1(int[] weight, int n, int maxWeight) {
		int sum = 0;
		int count = 0;
		for (int i = 0; i < n; i++) {
			sum += weight[i];//累加
			if (sum <= maxWeight) {//不超过承重上限
				count++;
			} else {
				break;
			}
		}
		return count;
	}
	
	public void useGreedyAlgorithmKnapsack1HaveCount() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		Obj[] weights = new Obj[N];
		int[] counts = new int[N];
		for (int i = 0; i < N; i++) {
			weights[i] = new Obj(i + 1, scanner.nextInt());
		}
		int maxWight = scanner.nextInt();
		Arrays.sort(weights);
		int res = GreedyAlgorithmKnapsack1HaveCount(weights, N, maxWight, counts);
		System.out.println(res);
		for (int i : counts) {
			if (i == 0) {
				break;
			}
			System.out.print(i + " ");
		}
	}
	
	
	public int GreedyAlgorithmKnapsack1HaveCount(Obj[] weights, int n, int maxWeight, int[] counts) {
		int sum = 0;
		int count = 0;
		for (int i = 0; i < n; i++) {
			sum += weights[i].weight;//累加
			if (sum <= maxWeight) {//不超过承重上限
				counts[count] = weights[i].index;
				count++;
			} else {
				break;
			}
		}
		return count;
	}
	
	private static class Obj implements Comparable<Obj> {
		int index;
		int weight;
		public Obj(int index, int weight) {
			this.index = index;
			this.weight = weight;
		}
		@Override
		public int compareTo(Obj other) {
			int x = this.weight - other.weight;
			if (x == 0) {
				return this.index - other.index;
			}
			return x;
		}
	}
}
